#define _CRT_SECURE_NO_WARNINGS 1
//#include <stdio.h>
//#include <stdlib.h>
//
//include<math.h>
//int main()
//{
    //
//    
//    int n, arr[105], flag[105];
//    scanf_s("%d", &n);
//
//    for (int i = 1; i <= n; i++)
//    {
//        scanf_s("%d", arr+i);
//    }
//    int ans = 0;
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= n; j++)
//        {
//            flag[j] = 0;
//        }
//        int num = 1, pos = i, sum = 0, cunt = 0;
//        while (1){
//            if (cunt == n || num > n)
//                break;
//                //濠电偞鎸搁幉锟犲垂濞嗘垹纾奸柟鎯х摠鐏?
//            if (flag[pos]==1)
//            {
//                if (pos == n)
//                    pos = 1;
//                else
//                    pos++;
//                continue;
//            }
//            if (num == arr[pos])
//            {
//                sum += arr[pos];
//                cunt++;
//                num = 1;
//                flag[pos] = 1;
//                if (pos == n)
//                {
//                    pos = 1;
//                }
//                else {
//                    pos++;
//                }
//            }
//            else{
//                num++;
//                if (pos == n)
//                    pos = 1;
//                else
//                    pos++;
//            }
//        }
//        if (sum > ans)
//            ans = sum;
//    }[]
//    printf("%d", ans);
//    return 0;
//}
//#include<stdio.h>
//#include<stdlib.h>
//
//int gcd(int i, int j)
//{
//	if (j == 0)
//		return i;
//	return gcd(j, i % j);
//}
//int main()
//{
//	int i, j,sum=0;
//	//i闂?闂佸憡甯掑Λ娆撴儊濠靛鏅悗鍏夋櫊瀹曟岸宕卞Δ鍐╂啢
//	for (i = 1; i <= 2020; i++)
//	{
//		for (j = 1; j <= 2020; j++)
//		{
//			if (gcd(i, j) == 1)
//			{
//				sum++;
//			}
//		}
//	}
//	printf("%d", sum);
//	return 0;
//}
//#include <stdio.h>
//#include <stdlib.h>
#include<math.h>
//int judge(int n)
//{
//    while (n)
//    {
//        if (n % 10 == 2 || n % 10 == 4)
//        {
//            return 0;
//        }
//        n /= 10;
//    }
//    return 1;
//}
//int main(int argc, char* argv[])
//{
//    int i, j, k;
//    int ans = 0;
//    for (i = 1; i <= 2019; i++)
//    {
//        for (j = 1; j <= 2019; j++)
//        {
//            k = 2019 - i - j;
//            if (judge(i) && judge(j) && judge(k))
//            {
//                if (i < j && j < k)
//                {
//                    ans++;
//                }
//            }
//        }
//    }
//    printf("%d\n", ans);
//    return 0;
//}

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>

//int main()
//{
//	int a, b, n;
//	scanf("%d %d %d", &a, &b, &n);
//	int m, z,t=0;
//	int sum = 0;
//	while (1)
//	{
//		for (m = 1; m <= 5; m++)
//		{
//			sum += a;
//			t++;
//			if (sum >= n)
//				break;
//		}
//		if (sum >= n)
//			break;
//		for (z = 1; z <= 2; z++)
//		{
//			sum += b;
//			t++;
//			if (sum >= n)
//				break;
//		}
//		if (sum >= n)
//			break;
//	}
//	printf("%d", t);
//	return 0;
//}
//先计算几周，在计算几天
int main()
{
	long long a, b, n;
	scanf("%d %d %d", &a, &b, &n);
	int t = 0;
	for (long long x = 1;x*a<=n; x++)
	{
		for (long long y = 1;y*b<=n; y++)
		{
			long long j = x * a;
			long long k = y * b;
			if ((j+k) == n)
			{
				t = x + y;
				break;
			}
		}
		if (t != 0)
			break;
	}
	printf("%d", t);
	return 0;
}
//#include <stdio.h>
//
//int main()
//{
//    long long a, b, n;
//    scanf("%lld %lld %lld", &a, &b, &n);
//
//    long long week = 5 * a + 2 * b;  // 每周总做题数
//    long long full_weeks = n / week;  // 完整周数
//    long long remaining = n % week;   // 剩余题数
//
//    long long days = full_weeks * 7;  // 完整周对应的天数
//
//    if (remaining > 0)  // 如果还有剩余题数
//    {
//        for (int i = 1; i <= 7; i++)  // 遍历一周的7天
//        {
//            if (i <= 5)  // 工作日（周1-5）
//                remaining -= a;
//            else         // 周末（周6-7）
//                remaining -= b;
//
//            days++;
//
//            if (remaining <= 0)  // 如果剩余题数完成，退出循环
//                break;
//        }
//    }
//
//    printf("%lld\n", days);
//    return 0;
//}
//婵炴垶姊圭换鍌烆敊閸岀偟宓佺紓浣股戦悡?
//#include <stdio.h>
//#include <stdlib.h>
//
//int main(int argc, char* argv[])
//{
//    int arr[8][9] = {
//                {4,9,2,3,5,7,8,1,6},
//                {8,3,4,1,5,9,6,7,2},
//                {6,1,8,7,5,3,2,9,4},
//                {2,7,6,9,5,1,4,3,8},
//                {4,3,8,9,5,1,2,7,6},
//                {8,1,6,3,5,7,4,9,2},
//                {6,7,2,1,5,9,8,3,4},
//                {2,9,4,7,5,3,6,1,8},
//    };
//    int j=0, sum = 0, a[9];
//    for (int i = 0; i < 9; i++)
//        scanf("%d", &a[i]);
//    for (int i = 0; i < 8; i++)
//    {
//        for (j = 0; j < 9; j++)//闂佸憡鐟禍鐐诧耿?闂佸憡绮岄惉鐓幟规径鎰Е鐎规繛?
//        {
//            if (a[j] > 0 && a[j] != arr[i][j])//婵炴垶鎸堕崐娑氱博閻斿吋鐒鹃柤鎭掑劜绗戦梺娲讳簽閸犳劖鏅堕悩璇插強妞ゆ牗绮嶉崺鍌炴煏?
//                break;
//        }
//        if (j == 9)
//        {
//            for (int k = 0; k < 9; k++)
//                a[k] = arr[i][k];
//            sum++;
//        }
//    }
//    if (sum == 1)
//        for (int i = 0; i < 9; i++)
//        {
//            if (i % 3 == 0) printf("\n");
//            printf("%d ", a[i]);
//        }
//    else
//        printf("Too Many");
//    return 0;
//}
//

////缂備礁鐭侀崕鑽ょ矓濞差亝鈷栫瑰嫭婢橀梾?
//#include<stdio.h>
//#include<stdlib.h>
//char arr[105][105];
//int visited[110][110];
//int a[4][2] =
//{
//{0,1},
//{1,0},
//{-1,0},
//{0,-1}
//};
//int n;
//int dfs(int ax, int ay)
//{
//	visited[ax][ay] = 1;
//	if (arr[ax][ay] == 'B')
//	{
//		return 0;
//	}
//	int d = n * n;/////??????
//	for (int i = 0; i < 4; i++)
//	{
//		int x1 = a[i][0] + ax;
//		int y1 = a[i][1] + ay;
//		if (visited[x1][y1] || x1 > n || y1 > n || x1 < 1 || y1 < 1)
//        {
//            continue;
//	    }
//		if (arr[ax][ay] != arr[x1][y1])
//		{
//		    int d1 = dfs(x1, y1) + 1;//闂備緡鍋呯敮鎺旂礊?
//		    d = (d1 < d) ? d1 : d;
//		    visited[x1][y1] = 0;
//		}
//    }
//}
//
//int main()
//{
//	int i, j, sum = 0;
//	int ax=0, ay=0;
//	scanf("%d", &n);
//	for (i = 0; i < n; i++)
//	{
//		for (j = 0; j < n; j++)
//		{
//			scanf("%c", &arr);
//		}
//		if (arr[i][j] == 'A')
//		{
//			ax = i;
//			ay = j;
//		}
//	}
//	int d = dfs(ax, ay);
//}





//#include <stdio.h>
//char g[110][110];
//int visited[110][110];
//int a[4][2] =
//{
//{0,1},闂?
//{1,0},婵?
//{-1,0},婵?
//{0,-1}閻?
//};
//int n;
//int dfs(int x, int y)
//{
//    visited[x][y] = 1;
//    if (g[x][y] == 'B')
//    {
//        return 0;
//    }
//    int d = n * n;
//    for (int i = 0; i < 4; i++)
//    {
//        int x1 = a[i][0] + x;
//        int y1 = a[i][1] + y;
//        if (visited[x1][y1] || x1 > n || y1 > n || x1 < 1 || y1 < 1)
//        {
//            continue;
//        }
//        if (g[x][y] != g[x1][y1])
//        {
//            int d1 = dfs(x1, y1) + 1;
//            d = (d1 < d) ? d1 : d;
//            visited[x1][y1] = 0;
//        }
//    }
//    return d;
//}
//
//int main()
//{
//    int ax, ay;
//    scanf("%d", &n);
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= n; j++)
//        {
//            scanf(" %c", &g[i][j]);
//            if (g[i][j] == 'A')
//            {
//                ax = i;
//                ay = j;
//            }
//        }
//    }
//    int d = dfs(ax, ay);
//    if (d == n * n)
//    {
//        printf("-1");
//    }
//    else
//    {
//        printf("%d", d);
//    }
//    return 0;
//}


//闂佹眹鍨婚崰鎰板垂?*3婵炴垶鎸哥粔褰掑闯閸涘﹤绶炵广儱妫欏▓鍫曟倵濞戞瑯娈橀柣鎾櫊濮婅偐鍠婃径宀顦柣搴ｆ暩椤㈠﹪锝炲Δ鍐／閻熶降鍊撳ù鍥侀幋锕违濞达絿枪閻忔瑩姊洪鐐珪婵炴潙顦辩划鍨緞?
//#include<stdio.h>
//#include<stdlib.h>
//#include<stdbool.h>
//
//int arr[3][3];
//int p[10];
//int i;
//int main()
//{
//	for (i = 1; i <= 10; i++)
//	{
//		p[i] = i;
//	}
//	do {
//		//闂佸憡甯楃粙鎴犵磽閹惧鈻旀繛鎴炴惄娴滅偤鎮￠埡鍛挀?
//		arr[1][1] = p[1], arr[1][2] = p[2], arr[1][3] = p[3];
//		arr[2][1] = p[4], arr[2][2] = p[5], arr[2][3] = p[6];
//		arr[3][1] = p[7], arr[3][2] = p[8], arr[3][3] = p[9];
//		int ok = true;//true闂佸搫瀚烽崹顖滃姬闁诲氦顕栭崑鍕緞閻旂厧妫?
//		int sum = arr[1][1] + arr[2][2] + arr[3][3];
//		if (sum != arr[1][3] + arr[2][3] + arr[3][1])
//			continue;
//		for (int i = 1; i <= 3; i++)
//		{
//			int tmp1 = 0, tmp2 = 0;//1闁荤偞绋忛崝搴ㄥΦ濮樿鲸鍋樼圭ｎ剛顦柣鐐寸◤閸斿酣濡靛璺虹?
//			for (int j = 1; j <= 3; j++)
//			{
//				tmp1 += arr[i][j];
//				tmp2 += arr[j][i];
//				if (tmp1 != sum || tmp1 != tmp2 || tmp2 != sum)
//				{
//					ok = false;
//				}
//			}
//			if (!ok)
//				continue;
//			//闂佹眹鍨婚崰鎰板垂濮樿泛绀傞柕濠忕畱缁楁捇鏌?
//			for (int i = 1; i <= 3; i++)
//			{
//				for(int j = 1; j <= 3; j++)
//				{
//					printf("\n");
//					printf("%d", arr[i][j]);
//				}
//			}
//			printf("\n");
//		}
//		
//
//	}while()
//	
//}
// erro
//#include <stdio.h>
//#include <stdbool.h>
//
//int arr[4][4]; // 濞达綀娉曢弫?1~3 闁汇劌瀚粭鍛村冀?
//int p[10];     // 濞达綀娉曢弫?1~9 闁汇劌瀚粭鍛村冀?
//
//void swap(int* a, int* b) {
//    int temp = *a;
//    *a = *b;
//    *b = temp;
//}
//
//bool checkMagicSquare(int* p) {
//    int index = 1;
//    for (int i = 1; i <= 3; i++) {
//        for (int j = 1; j <= 3; j++) {
//            arr[i][j] = p[index++];
//        }
//    }
//
//    int sum = arr[1][1] + arr[2][2] + arr[3][3]; // 濞戞捁顕ч顔炬喆閹烘柨娈
//    if (sum != arr[1][3] + arr[2][2] + arr[3][1]) return false; // 闁告搩鍨伴顔炬喆閹烘柨娈
//
//    for (int i = 1; i <= 3; i++) {
//        int rowSum = 0, colSum = 0;
//        for (int j = 1; j <= 3; j++) {
//            rowSum += arr[i][j];
//            colSum += arr[j][i];
//        }
//        if (rowSum != sum || colSum != sum) return false;
//    }
//
//    return true;
//}
//
//void printMagicSquare(int* p) {
//    int index = 1;
//    for (int i = 1; i <= 3; i++) {
//        for (int j = 1; j <= 3; j++) {
//            printf("%d ", p[index++]);
//        }
//        printf("\n");
//    }
//    printf("\n");
//}
//
//int cnt = 0;
//void permute(int* p, int start, int end) {
//    if (start == end) {
//        if (checkMagicSquare(p)) {
//            printMagicSquare(p);
//            cnt++;
//            if (cnt >= 1) return; // 闁告瑯浜ｇ欢顓㈠礄鏉炴壆顏卞☉鎿冧簷缁￠悗璇″亜婢剁喖寮?
//        }
//    }
//    else {
//        for (int i = start; i <= end; i++) {
//            swap(&p[start], &p[i]);
//            permute(p, start + 1, end);
//            swap(&p[start], &p[i]); // 闁搞儳鍋為崙?
//        }
//    }
//}
//
//int main() {
//    // 闁告帗绻傞～鎰板礌?p 闁轰焦澹嗙划?
//    for (int i = 1; i <= 9; i++) {
//        p[i] = i;
//    }
//
//    // 閻犲洩顕цぐ鍥偨閵婏箑鐓曢弶鍫熸尭閸欏棝鎯?3x3 闁活厸鏅犲Ο
//    printf("閻犲洨鏌夌欢顓㈠礂?3x3 闁活厸鏅犲Ο闁?~9 闁汇劌瀚弳鐔烘稒顨愮槐婵堢矚閻戞澹愰柛鎺戞濞堁囨晬婢舵稓绐梊n");
//    for (int i = 1; i <= 3; i++) {
//        for (int j = 1; j <= 3; j++) {
//            scanf("%d", &arr[i][j]);
//        }
//    }
//learn c
//
//    // 閻忓繐妫涢弫銈夊箣閻ゎ垳缈婚柛蹇嬪劤濞堟垿鎯岄埡鍛枅閻庢稒锚閸嬪秹宕?p 闁轰焦澹嗙划宥嗙▔?
//    int index = 1;
//    for (int i = 1; i <= 3; i++) {
//        for (int j = 1; j <= 3; j++) {
//            p[index++] = arr[i][j];
//        }
//    }
//
//    // 婵☆偊寮婚妷銊х炕闁稿繈鍎冲▓鎴﹀极閺夎法鎽熼柡鍕靛灠閹線宕ラ崼鐔恒
//    bool valid = true;
//    int count[10] = { 0 }; // 闁烩偓鍔嬬花顒螞闁哄被鍎查弳鐔烘稒顨嗗Σ鎼佸触閿曞倸娅㈠?
//    for (int i = 1; i <= 9; i++) {
//        if (p[i] != 0 && (p[i] < 1 || p[i] > 9 || count[p[i]] > 0)) {
//            valid = false;
//            break;
//        }
//        if (p[i] != 0) count[p[i]]++;
//    }
//
//    if (!valid) {
//        printf("閺夊牊鎸搁崣鍡涙儍閸曨剚娈堕悗娑欍仦缁楀宕ラ崼鐔恒婇柨娑楁祰椤曨剛娑甸鑽ょ閺夊牊鎸搁崣?1~9 闁汇劌瀚粭澶愭煂瀹ュ拋妲婚柡浣规緲閻⊙囧Υ娣囨悏");
//        return 1;
//    }
//
//    // 闁汇垻鍠愰崹姘跺礂閵婏箑绗撻柛鎺擃殔閼荤喎螞闁哄被鍎扮弧閻庤鍋勬径鐔煎棘?
//    permute(p, 1, 9);
//
//    return 0;
//}
//#include <stdio.h>
//#include <stdbool.h>
//
//int arr[4][4]; // 濞达綀娉曢弫?1~3 闁汇劌瀚粭鍛村冀?
//int p[10];     // 濞达綀娉曢弫?1~9 闁汇劌瀚粭鍛村冀?
//
////闁?
//void swap(int* a, int* b) {
//    int temp = *a;
//    *a = *b;
//    *b = temp;
//}
//
////闁?
//bool checkMagicSquare(int* p) {
//    int index = 1;
//    for (int i = 1; i <= 3; i++) {
//        for (int j = 1; j <= 3; j++) {
//            arr[i][j] = p[index++];
//        }
//    }
//
//    int sum = arr[1][1] + arr[2][2] + arr[3][3]; // 濞戞捁顕ч顔炬喆閹烘柨娈
//    if (sum != arr[1][3] + arr[2][2] + arr[3][1]) return false; // 闁告搩鍨伴顔炬喆閹烘柨娈
//
//    for (int i = 1; i <= 3; i++) {
//        int rowSum = 0, colSum = 0;
//        for (int j = 1; j <= 3; j++) {
//            rowSum += arr[i][j];
//            colSum += arr[j][i];
//        }
//        if (rowSum != sum || colSum != sum) return false;
//    }
//
//    return true;
//}
//
////闁?
//void printMagicSquare(int* p) {
//    int index = 1;
//    for (int i = 1; i <= 3; i++) {
//        for (int j = 1; j <= 3; j++) {
//            printf("%d ", p[index++]);
//        }
//        printf("\n");
//    }
//    printf("\n");
//}
//
//
////閼?
//int cnt = 0;
//void permute(int* p, int start, int end) {
//    if (start > end) { // 濞ｅ浂鍠楅弫鑲╃磼閸噥鍓鹃柡澶嗗弶顐
//        if (checkMagicSquare(p)) {
//            printMagicSquare(p);
//            cnt++;
//            if (cnt >= 1) return; // 闁告瑯浜ｇ欢顓㈠礄鏉炴壆顏卞☉鎿冧簷缁￠悗璇″亜婢剁喖寮?
//        }
//        return;
//    }
//
//    if (p[start] != 0) {
//        // 濠碘冲归悘澶庛亹閹惧啿顤呭ù锝呯Ф閻ゅ棗顔忛懠顒傜梾闁哄牆顦涵椋庣闁烩晛鐡ㄧ敮瀛樺緞閸曨厽鍊炲☉鎾愁儎缁斿瓨绋夐鍐Т缂?
//        permute(p, start + 1, end);
//    }
//    else {
//        // 濠碘冲归悘澶庛亹閹惧啿顤呭ù锝呯Ф閻ゅ棝寮?0闁挎稑鑻惃鍓ф嫚閺囩儑缍栭柛?1~9 闁汇劌瀚弳鐔?
//        for (int k = 1; k <= 9; k++) {
//            bool used = false;//闁轰焦婢橀悺褍鈻介埄鍐╃畳閻炴凹鍋傛繛鍥偨?
//            for (int j = 1; j <= 9; j++) {
//                if (p[j] == k) {
//                    used = true;//闁烩晛鎽滈悺鎴濐啅閼碱剛鐥呴悶姘煎亗婵炲洭鎮?
//                    break;
//                }
//            }
//            if (!used) {//闁轰焦婢橀悺顪辨繛灞稿墲濠浣烘偖椤愨斥枏闁汇埄鐓夌槐婵囩箙椤愩垹甯犻柡浣规緲閻?
//                p[start] = k; // 濠靛鍋勯崢鏍极閺夎法鎽
//                permute(p, start + 1, end); // 闂侇偅甯掔紞濠冨緞閸曨厽鍊炲☉鎾愁儎缁斿瓨绋夐鍐Т缂?
//                p[start] = 0; // 闁搞儳鍋為崙?
//            }
//        }
//    }
//}
//
//int main() {
//    // 闁告帗绻傞～鎰板礌?p 闁轰焦澹嗙划?
//    for (int i = 1; i <= 9; i++) {
//        p[i] = i;
//    }
//
//    // 閻犲洩顕цぐ鍥偨閵婏箑鐓曢弶鍫熸尭閸欏棝鎯?3x3 闁活厸鏅犲Ο
//    printf("閻犲洨鏌夌欢顓㈠礂?3x3 闁活厸鏅犲Ο闁?~9 闁汇劌瀚弳鐔烘稒顨愮槐? 閻炴稏鍔庨妵姘跺嫉椤忓嫸缍栭柛蹇撴嫅缁辨繄绮氶悜妯煎闁告帒妫濆▓褔鏁嶆径娑氱獥\n");
//    for (int i = 1; i <= 3; i++) {
//        for (int j = 1; j <= 3; j++) {
//            scanf("%d", &arr[i][j]);
//        }
//    }
//
//    // 閻忓繐妫涢弫銈夊箣閻ゎ垳缈婚柛蹇嬪劤濞堟垿鎯岄埡鍛枅閻庢稒锚閸嬪秹宕?p 闁轰焦澹嗙划宥嗙▔?
//    int index = 1;
//    for (int i = 1; i <= 3; i++) {
//        for (int j = 1; j <= 3; j++) {
//            p[index++] = arr[i][j];
//        }
//    }
//
//    //闁?
//    // 婵☆偊寮婚妷銊х炕闁稿繈鍎冲▓鎴﹀极閺夎法鎽熼柡鍕靛灠閹線宕ラ崼鐔恒
//    bool valid = true;
//    int count[10] = { 0 }; // 闁烩偓鍔嬬花顒螞闁哄被鍎查弳鐔烘稒顨嗗Σ鎼佸触閿曞倸娅㈠璺虹▌缁辨繄鎷犻妷锔芥缂備礁瀚ぐ褔寮弶璺ㄦ憻闁告垼娅ｉ獮鍥儍閸曨剦鍋ч柡浣藉焽?
//    for (int i = 1; i <= 9; i++) {
//        if (p[i] != 0 && (p[i] < 1 || p[i] > 9 || count[p[i]] > 0)) {//濠碘冲归悘澶愬礄閾忕懓绠涘☉鎾卞栭鍏肩閵夈倗鐟愬☉鎾崇У瀵呮惥閾忣偅钂嬪ù鐘插濞插潡骞掗¨鈺甧ak
//            valid = false;
//            break;
//        }
//        if (p[i] != 0) count[p[i]]++;//濞戞挻绋夐鍫熷0闁汇劌瀚弳鐔烘稒顨愮槐婵嬪礄閾忕懓绠涢柣銊ュ椤愬ジ寮?+闁靛棗鍊规俊绔漑i]闁汇劌瀚悡搴ｇЪ濞达絾绔穙unt闁汇劌瀚粭鍛村冀閸ラ绀夐柛锔规殮闁靛棙浜奸柕鍡樺灱缁绘牗绋夐鍐憮闁哄秴娲ｇ粭鍛存晬瀹椤戝洦绋夋繛鍡忓啿姣夐柣婊呭濡?闁挎稑鐬奸鍥ㄧ鐏炵虎鍋++闁挎稑鑻崹浠嬪棘椤撶喐钂嬪ù鐘虫构缁楀饪伴檱閸愬鎯勭涙ê澶峛reak
//    }
//
//    if (!valid) {
//        printf("閺夊牊鎸搁崣鍡涙儍閸曨剚娈堕悗娑欍仦缁楀宕ラ崼鐔恒婇柨娑楁祰椤曨剛娑甸鑽ょ閺夊牊鎸搁崣?1~9 闁汇劌瀚粭澶愭煂瀹ュ拋妲婚柡浣规緲閻⊙囧Υ娣囨悏");
//        return 1;
//    }
//
//    // 闁汇垻鍠愰崹姘跺礂閵婏箑绗撻柛鎺擃殔閼荤喎螞闁哄被鍎扮弧閻庤鍋勬径鐔煎棘?
//    printf("闁告瑯鍨甸崗姗鎯冮崟顏嗙槇閻庤鍋勬径鐔煎棘閻у摜绐梊n");
//    permute(p, 1, 9);
//
//    if (cnt == 0) {
//        printf("闁哄牜浜濇竟姗宕氶幍顕呭剨闁告艾鐗婂顖涚閸撲焦鐣卞☉鏃绻傞鍌炵嵁缂佹ɑ鐓欓柕鍡曠箰n");
//    }
//
//    return 0;
//}
//#include<stdio.h>
//#include<stdlib.h>
//
//int n, m;
//int i, j;
//int arr[100][100];
//int ans[100][100];
//int main()
//{
//    scanf("%d %d\n", &n, &m);
//    for (i = 0; i < n; i++) {
//        for (j = 0; j < n; j++)
//        {
//            scanf("%d", &arr[i][j]);
//        }
//    }
//    for (i = 0; i < m; i++) {
//        for (j = 0; j < m;j++)
//        {
//            scanf("%d ", &ans[i][j]);
//        }
//    }
//
//}
//#include<stdio.h>
//#include<stdlib.h>
//#include<stdbool.h>
//
//#define MAX_N 1005
//int n, m;
//int i, j;
//char maze[MAX_N][MAX_N];//閺夆晛鍢查?
//bool visited[MAX_N][MAX_N];//闁哄嫷鍨伴幆浣烘偖椤愩儺鍟忛梻鍌ゅ枦缁?
//int count = 0;//閻犱焦婢樼紞宥夊冀閻撳海鎽嶉柡?
//
////闁哄倻鎳撻幃婊堝极閹殿喚鐭嬮柨娑欑煯缁楀倹绋夌ｎ亙绠柛?
//int dx[4] = { -1,1,0,0 };
//int dy[4] = { 0,0,-1,1 };
//
//void dfs(int x, int y)
//{
//    visited[x][y] = true;//鐎规瓕灏欑划锛勬偖椤愩儺鍟忛梻?
//    count++; //閻犱礁娼″Λ鑸电▔椤忓懏娈 + 1
//        //闂侇剙绉村缁樼▔婵犱胶鐟撶归潻绠戣ぐ鎼佸炊濞戞鍤嬮柡鍌滄嚀閹?
//        for (i = 0; i < 4; i++)
//        {
//            int nx = x + dx[i];
//            int ny = y + dy[i];
//            //婵☆偊寮婚妷銊х彾闁伙絽鏈顖涚?
//            if (nx >= 1 && nx <= n && ny >= 1 && ny <= n)
//            {
//                if (maze[x][y] != visited[x][y] && !visited[x][y])
//                    dfs(nx, ny);//闂侇偅甯掔紞?
//            }
//        }
//}
//
//int main()
//{
//    scanf("%d %d\n", &n, &m);//闁?
//    for (i = 1; i <= n; i++)
//    {
//        scanf('%s', maze[i] + 1);//i缂佹稑顦花?閻忓繗椴稿Σ鍝ョ箔椤戣法顏遍悶娑樿閸屾艾璁插ù鐘劥缁额參宕楅妷銈囩檶缂備礁鐡ㄩ弳鐔虹磼閸曞墎绀夐悹鍝勭枃缁诲啰绮?闁告帗銇?
//    }
//    while (m--)
//    {
//        int x, y;
//        scanf("%d %d", &x, &y);
//        //闁告帗绻傞～鎰板礌?
//        count = 0;
//        for (i = 1; i <= n; i++)
//        {
//            for (j = 1; j <= n; j++)
//            {
//                visited[i][j] = false;//閺夆晜蓱濠顓犳偖椤愶絿鍨奸悹?
//            }
//        }
//        dfs(x, y);
//    }
//}

//#include <stdio.h>
//#include <stdbool.h>
//#define MAX_N 1005
//int arr[4][4]; // 婵炶揪缍濞夋洟寮?1~3 闂佹眹鍔岀氼亞绮崨鏉戝唨?
//int p[10];     // 婵炶揪缍濞夋洟寮?1~9 闂佹眹鍔岀氼亞绮崨鏉戝唨?
//int n, m;
//char maze[MAX_N][MAX_N]; // 閻庢稒锚閸嬪秵娼诲畡閭﹀敨
//bool visited[MAX_N][MAX_N]; // 闁哄秴娲╅鍥及椤栨碍鍎婇悹浣告健濡埖娼?
//int count; // 閻犱焦婢樼紞宥嗙鎼淬倖宕抽柣鎰嚀閸ゎ參宕ｉ幋锝呭幋缂佸顕ф慨鈺呭礆閹殿喗鐣遍柡宥囧帶閻℃瑩寮?
//
//// 闁哄倻鎳撻幃婊堝极閹殿喚鐭嬮柨娑欑煯缁楀倹绋夌ｎ亙绠柛?
//int dx[4] = { -1, 1, 0, 0 };
//int dy[4] = { 0, 0, -1, 1 };
//
//// DFS 闁告垼濮ら弳?
//void dfs(int x, int y) {
//    visited[x][y] = true; // 闁哄秴娲╅鍥亹閹惧啿顤呴柡宥囧帶閻℃瑦绋夐崫鍕殥閻犱礁娼″Λ?
//    count++; // 濠⒀呭仜婵偟鎷嬮埄鍐╂闁?
//    int sum = arr[1][1] + arr[2][2] + arr[3][3]; // 婵炴垶鎹侀褔顢氶鐐枂闁圭儤鏌ㄥ▓?
//    if (sum != arr[1][3] + arr[2][2] + arr[3][1]) return false; // 闂佸憡鎼╅崹浼搭敋椤旂偓鍠嗛柟鐑樻煥濞?
//
//    // 闂侇剙绉村濠氬炊濞戞鍤嬮柡鍌滄嚀閹?
//    for (int i = 0; i < 4; i++) {
//        int nx = x + dx[i];//0
//        int ny = y + dy[i];//1
//
//        // 婵☆偊寮婚妷銊х彾闁伙絽鏈顖涚?
//        if (nx >= 1 && nx <= n && ny >= 1 && ny <= n) {
//            // 婵☆偊寮婚妷顬晠宕濋妸锔借拫濞寸姾顔愮槐鎷屻亹閹惧啿顤呴柡宥囧帶閻℃瑦绋夋惔锝嗙ゲ闂侇厾绮悧鍝ユ稒鍔楀▓鎴﹀磹闂傚鐟濋柛?
//            if (maze[x][y] != maze[nx][ny] && !visited[nx][ny]) {
//                dfs(nx, ny); // 闂侇偅甯掔紞濠勬嫬閸愵亝鏆 DFS
//            }
//        }
//    }
//}
//int main() {
//    // 閻犲洩顕цぐ鍥ㄦ綇閹惧啿寮
//    scanf("%d %d", &n, &m);
//    for (int i = 1; i <= n; i++) {
//        scanf("%s", maze[i] + 1); // 濞寸姴娴烽?1 闁告帗顨呯槐鎴炴叏鐎ｎ亞鎽犻柛?
//    }
//
//    // 濠㈣泛瀚幃濠傂掕箛搴ㄥ殝閻犲洢鍨藉Λ?
//    while (m--) {
//        int x, y;
//        scanf("%d %d", &x, &y);
//
//        // 闁告帗绻傞～鎰板礌?
//        count = 0;
//        for (int i = 1; i <= n; i++) {
//            for (int j = 1; j <= n; j++) {
//                visited[i][j] = false;
//            }
////闂佹眹鍨婚崰鎰板垂濮樿泛绀傞柕濠忕畱缁楁捇鏌涢幒鎿冩當闁归攱婢樿灋闂佸搫琚崕鎻捨ｉ幖浣歌Е闁挎棁鍎荤粈瀣槈閺冪换鍌烆敊閸岀偟宓佺紓浣股戦悡娆撴煏?
//void permute(int* p, int start, int end) {
//    if (start == end) {
//        if (checkMagicSquare(p)) {
//            printMagicSquare(p);
//        }
//    }
//    else {
//        for (int i = start; i <= end; i++) {
//            swap(&p[start], &p[i]);
//            permute(p, start + 1, end);
//            swap(&p[start], &p[i]); // 闂佹悶鍎抽崑鐐哄礄?
//
//        }
//
//        // 閻犲鍟伴弫?DFS
//        dfs(x, y);
//
//
//        // 閺夊牊鎸搁崵顓犵磼閹惧浜
//        //count -= 1;
//        printf("%d\n", count);
//
//    permute(p, 1, 9); // 闂佹眹鍨婚崰鎰板垂濮樿泛绀傞柕濠忕畱缁楁捇鏌涢幒鎿冩當闁艰崵鍠庤灋闂佸搫琚崕鎵姬闁诲氦顕栭崑鍕緞閻旂厧妫?
//
//    return 0;
//}
//
//
//
////闂佺ǹ绻堥崝宥囨暜閹捐绀?
//#include <stdio.h>
//#include <stdbool.h>
//
//int arr[4][4]; // 婵炶揪缍濞夋洟寮?1~3 闂佹眹鍔岀氼亞绮崨鏉戝唨?
//int p[10];     // 婵炶揪缍濞夋洟寮?1~9 闂佹眹鍔岀氼亞绮崨鏉戝唨?
//
////闂?
//void swap(int* a, int* b) {
//    int temp = *a;
//    *a = *b;
//    *b = temp;
//}
//
////闂?
//bool checkMagicSquare(int* p) {
//    int index = 1;
//    for (int i = 1; i <= 3; i++) {
//        for (int j = 1; j <= 3; j++) {
//            arr[i][j] = p[index++];
//        }
//    }
//
//    int sum = arr[1][1] + arr[2][2] + arr[3][3]; // 婵炴垶鎹侀褔顢氶鐐枂闁圭儤鏌ㄥ▓?
//    if (sum != arr[1][3] + arr[2][2] + arr[3][1]) return false; // 闂佸憡鎼╅崹浼搭敋椤旂偓鍠嗛柟鐑樻煥濞?
//
//    for (int i = 1; i <= 3; i++) {
//        int rowSum = 0, colSum = 0;
//        for (int j = 1; j <= 3; j++) {
//            rowSum += arr[i][j];
//            colSum += arr[j][i];
//        }
//        if (rowSum != sum || colSum != sum) return false;
//    }
//
//    return true;
//}
//
////闂?
//void printMagicSquare(int* p) {
//    int index = 1;
//    for (int i = 1; i <= 3; i++) {
//        for (int j = 1; j <= 3; j++) {
//            printf("%d ", p[index++]);
//        }
//        printf("\n");
//    }
//    printf("\n");
//}
//
//
////闁?
//int cnt = 0;
//void permute(int* p, int start, int end) {
//    if (start > end) { // 婵烇絽娴傞崰妤呭极閼测晝纾奸柛顐ゅ櫏閸撻箖鏌℃径鍡楀级椤?
//        if (checkMagicSquare(p)) {
//            printMagicSquare(p);
//            cnt++;
//            if (cnt >= 1) return; // 闂佸憡鐟禍锝囨椤撱垹绀勯弶鐐村椤忓崬鈽夐幙鍐х胺缂侊繝鎮楃拠鈥充簻濠㈠墎鍠栧?
//        }
//        return;
//    }
//
//    if (p[start] != 0) {
//        // 婵犵鍐插綊鎮樻径搴涗汗闁规儳鍟块·鍛归敐鍛ら柣銈呮椤斿繘鎳犻鍌滄⒕闂佸搫鐗嗛ˇ顖滄兜妞嬪海顦梺鐑╂櫅閻°劎鏁涙ê绶為柛鏇ㄥ幗閸婄偛鈽夐幘鎰佸剮缂佹柨鐡ㄧ粙澶愵敂閸愵亞孝缂?
//        permute(p, start + 1, end);
//    }
//    else {
//        // 婵犵鍐插綊鎮樻径搴涗汗闁规儳鍟块·鍛归敐鍛ら柣銈呮瀵?0闂佹寧绋戦懟顖炴儍閸撗勫珰闁哄洨鍎戠紞鏍煕?1~9 闂佹眹鍔岀氼參寮抽悢?
//        for (int k = 1; k <= 9; k++) {
//            bool used = false;//闂佽桨鐒﹀姗鎮鸿閳讳粙鍩勯崘鈺冪暢闁荤偞鍑归崑鍌涚箾閸ヮ剚鍋?
//            for (int j = 1; j <= 9; j++) {
//                if (p[j] == k) {
//                    used = true;//闂佺儵鏅涢幗婊堟偤閹存繍鍟呴柤纰卞墰閻ュ懘鎮跺鐓庝簵濠电偛娲幃?
//                    break;
//                }
//            }
//            if (!used) {//闂佽桨鐒﹀姗鎮洪—杈ㄧ箾鐏炵ǹ澧叉繝娴ｇ儤鍋栨い鎰ㄦ枼鏋忛梺姹囧焺閻撳妲愬┑鍥╃畽妞ゆ劑鍨圭敮鐘绘煛娴ｈ绶查柣?
//                p[start] = k; // 婵犻潧顦介崑鍕储閺嶎厼鏋侀柡澶庢硶閹?
//                permute(p, start + 1, end); // 闂備緡鍋呯敮鎺旂礊婵犲啫绶為柛鏇ㄥ幗閸婄偛鈽夐幘鎰佸剮缂佹柨鐡ㄧ粙澶愵敂閸愵亞孝缂?
//                p[start] = 0; // 闂佹悶鍎抽崑鐐哄礄?
//            }
//        }
//    }
//}
//
//int main() {
//    // 闂佸憡甯楃换鍌烇綖閹版澘绀?p 闂佽桨鐒︽竟鍡欏垝?
//    for (int i = 1; i <= 9; i++) {
//        p[i] = i;
//    }
//
//    // 闁荤姴娲╅褑銇愰崶顒佸仺闁靛⿵绠戦悡鏇㈠级閸喐灏柛娆忔閹?3x3 闂佹椿鍘搁弲鐘参
//    printf("闁荤姴娲ㄩ弻澶屾椤撱垹绀?3x3 闂佹椿鍘搁弲鐘参熼梺?~9 闂佹眹鍔岀氼參寮抽悢鐑樼⊕椤ㄦ劗妲? 闁荤偞绋忛崝搴ㄥΦ濮樿泛瀚夋い蹇撳缂嶆牠鏌涜箛鎾村珔缂佽鲸绻勭划姘舵倻濡厧顥曢梺鍛婂笒濡繂鈻撹閺佸秵寰勫☉姘辩崶\n");
//    for (int i = 1; i <= 3; i++) {
//        for (int j = 1; j <= 3; j++) {
//            scanf("%d", &arr[i][j]);
//        }
//    }
//
//    // 闁诲繐绻愬Λ娑㈠极閵堝绠ｉ柣銈庡灣缂堝鏌涜箛瀣姢婵炲牊鍨块幆宀勫煛閸涱喒鏋呴柣搴㈢⊕閿氶柛瀣Ч瀹?p 闂佽桨鐒︽竟鍡欏垝瀹ュ棛鈻?
//    int index = 1;
//    for (int i = 1; i <= 3; i++) {
//        for (int j = 1; j <= 3; j++) {
//            p[index++] = arr[i][j];
//        }
//    }
//
//    //闂?
//    // 濠碘槅鍋婂濠氬Ψ閵娧呯倳闂佺ǹ绻堥崕鍐测枔閹达箑鏋侀柡澶庢硶閹界喖鏌￠崟闈涚仩闁诡垯绶氬畷銉╁醇閻旀亽?
//    bool valid = true;
//    int count[10] = { 0 }; // 闂佺儵鍋撻崝瀣姳椤掕灋闂佸搫琚崕鏌ュ汲閻旂儤绋掗〃鍡椢ｉ幖浣歌Е闁挎洖鍊稿▍銏狀熆鐠鸿櫣鈻岀紒杈ㄧ箘閹风娀濡烽敂鑺ヮ啀缂傚倷绀佺氼剝銇愯瀵偊寮剁捄銊︽喕闂佸憡鍨煎▍锝夌嵁閸ヮ剚鍎嶉柛鏇ㄥ墻閸嬔囨煛娴ｈ棄鐒?
//    for (int i = 1; i <= 9; i++) {
//        if (p[i] != 0 && (p[i] < 1 || p[i] > 9 || count[p[i]] > 0)) {//婵犵鍐插綊鎮樻径鎰闁惧繒鎳撶粻娑樷槈閹惧崬鏍敃閸忚偐顩烽柕澶堝楅悷鎰槈閹惧磭校鐎殿啫鍛儱闁惧浚鍋呴拏瀣归悩鎻掝暢婵炴彃娼￠獮鎺椔ㄩ埡鐢k
//            valid = false;
//            break;
//        }
//        if (p[i] != 0) count[p[i]]++;//婵炴垶鎸荤粙澶愵敂閸喎顫梺姹囧妼鐎氼參寮抽悢鐑樼⊕椤ㄦ劗妲愬┑瀣闁惧繒鎳撶粻娑㈡煟閵娿儱顏い鎰偢瀵?+闂侀潧妫楅崐瑙勪繆缁旀紤i]闂佹眹鍔岀氼剟鎮℃惔锝囆繛杈剧稻缁旂unt闂佹眹鍔岀氼亞绮崨鏉戝唨闁搞儵顥撶粈澶愭煕閿旇娈梺闈涙娴滃ジ鏌曢崱妯虹伇缂佺粯鐗楃粙澶愵敂閸愵亞鎲梺鍝勭Т濞诧絿绮崨瀛樻櫖鐎规い鎴濇处缁嬪绻涢崱蹇撳暱濮ｅ鏌ｅ⿰鍛暭婵?闂佹寧绋戦惉濂割敄閸ャ劎顩查悘鐐佃檸閸?+闂佹寧绋戦懟顖炲垂娴犲妫樻い鎾跺枑閽傚霉閻樿櫕鏋勭紒妤顦オ浼存闁告劕顭烽幆鍕稒锚婢跺硾reak
//    }
//
//    if (!valid) {
//        printf("闁哄鐗婇幐鎼佸矗閸℃稒鍎嶉柛鏇ㄥ墯濞堝爼鎮楀☉娆嶄沪缂佹顦靛畷銉╁醇閻旀亽濠囨煥濞戞绁版い鏇ㄥ墰濞戠敻顢欓懡銈囶啍闁哄鐗婇幐鎼佸矗?1~9 闂佹眹鍔岀氼亞绮径鎰厒鐎广儱鎷嬪Σ濠氭煛娴ｈ绶查柣鈯欏洤违濞ｅ洦鎮");
//        return 1;
//    }
//
//    // 闂佹眹鍨婚崰鎰板垂濮樿泛绀傞柕濠忕畱缁楁捇鏌涢幒鎿冩當闁艰崵鍠庤灋闂佸搫琚崕鎵姬闁诲氦顕栭崑鍕緞閻旂厧妫?
//    printf("闂佸憡鐟崹鐢稿礂濮楅幆鍐礋椤忓棛妲囬柣搴ゎ嚃閸嬪嫭寰勯悢鐓庢闁谎冩憸缁愭n");
//    permute(p, 1, 9);
//
//    if (cnt == 0) {
//        printf("闂佸搫鐗滄禍婵囩珶濮楀畷姘跺箥椤曞懎鍓ㄩ梺鍛婅壘閻楀﹤顭囬娑氼浄闁告挷鐒﹂悾鍗炩槈閺冪换鍌烆敊閸岀偟宓佺紓浣股戦悡娆撴煏閸℃洜绠皀");
//    }
//
//    return 0;
//}
//#include<stdio.h>
//#include<stdbool.h>
//
//#define MAX_N 100
//int n, k;
//int ans[MAX_N];
//int arr[MAX_N][MAX_N];
//int p[] = { 0 };
//
//void dfs(int* p, int start, int end)
//{
//    for (k = 1; k <= end; k++)
//    {
//        bool used = false;
//        for (int j = 1; j <= end; j++)
//        {
//            if (p[j] == k)
//                used = false;
//            break;
//        }
//        if (!used)
//        {
//            int q=p[start] ;
//            p[start] = k;
//            dfs(p, start + 1, end);
//            p[start] = q;
//        }
//   }
//    
//}
//
//int main()
//{
// 
//    for (int i = 1; i <= n; i++)
//    {
//        scanf("%d", &n);
//    }
//    for (int i = 1; i <= n; i++)
//    {
//        //閻忓繐妫滅欢顓㈠礂閵壯勭暠闁轰焦婢橀悺褏娑櫳戦弬渚宕烽埡顒勫极閹殿喚鐭嬪☉?
//        p[i] = i;
//    }
//
//    bool vaild = true;
//    int count[] = { 0 };//婵☆偊寮婚妷锔叫﹂柛姘剧畵閸ｅ憡寰?
//    for (int i = 1; i <= n; i++)
//    {
//        if (p[i]<1 || p[i]>n || count[p[i]] > 0)
//        {
//            vaild = false;
//            break;
//        }
//        if (p[i] != 0)
//            count[p[i]]++;
//    }
//        dfs(p, 1, n);
//
//        int indext = 1;
//        for (int i = 1; i <= n; i++)
//        {
//            for (int j = 1; j <= n; j++)
//            {
//                printf("%d ", p[indext++]);
//            }
//            printf("\n");
//        }
//        printf("\n");
//}
//#include<stdio.h>
//#include<stdbool.h>
//#define MAX_N 10
//int n;
//int p[MAX_N];//閻庢稒锚閸嬪秹宕烽妸銉хЪ闁告挸绉跺▓鎴﹀极閹殿喚鐭
//bool used[MAX_N];//閻犱焦婢樼紞宥囨偖椤愨斥枏闁?
//
//void dfs(int start)
//{
//	if (start > n)
//	{
//		for (int i = 1; i <= n; i++)
//		{
//			printf("%5d", p[i]);
//		}
//		printf("\n");
//		return;
//	}
//	for (int k = 1; k <= n; k++)
//	{
//		if (!used[k])
//		{
//			p[start] = k;
//			used[k] = true;
//			dfs(start + 1);
//			used[k] = false;
//		}
//	}
//}
//
//int main()
//{
//	scanf("%d", &n);
//	//闁告帗绻傞～鎰板礌?
//	for (int i = 1; i <= n; i++)
//	{
//		used[i] = false;
//	}
//	//閻犲鍟伴弫?
//	dfs(1);
//}






//#include<stdio.h>
//#include<stdlib.h>
//#include<stdbool.h>
//#define MAX_N 10
//
//int compare(const void* a, const void* b)
//{
//	int* planeA = (int*)a;
//	int* planeB = (int*)b;
//	if (planeA[0] != planeB[0])
//	{
//		return planeA[0] - planeB[0];//濞戞挸绉跺ù澶愬触鐏炴儳鐦婚柣鎾楀啫鐓傞弶鍫㈠亾濡炲倿姊?
//	}
//	else {
//		return planeA[1] - planeB[1];//闁烩晝枪閹捇骞愭径灞藉季闁烩晜蓱濡棝寮崼鏇燂紵
//	}
//}
//
//bool Check_Plane(int arr[][3], int m)
//{
//	qsort(arr, m, sizeof(arr[0]), compare);
//	int availableTime = 0;//閻犵儤鍨挎禍楣冨矗椤栨粍鏆忛柡鍐ㄧ埣濡?
//	for (int i = 0; i < m; i++)
//	{
//		int Ti = arr[i][0];//闁告帗濯介幓顏堝籍閸洘锛
//		int Di = arr[i][1];//闁烩晜蓱濡棝寮崼鏇燂紵
//		int Li = arr[i][2];//闂傚嫬绉烽幆銈夊籍閸洘锛
//
//		int earlyTime = Ti;
//		int lasteTime = Ti + Di;
//
//		//濠碘冲归悘澶屾崉閹达缚澹曢柣銊ュ瑜版煡鎮介妸锔筋槯闂傚倸鐡ㄥΛ顓熺鎼淬垺浠橀柡鍐ｆ櫊濡剧兘鎷冮悾灞剧暠闁哄啫鐖煎Λ鍧楁晬鐏炶棄鐏熼柛娆樺灣閺併倝寮寸涙ɑ鐓闁哄啫鐖煎Λ鍧楁晬閻曞倻鍚归柨娑氬櫐缁辩敻鏁?
//		if (availableTime < earlyTime)
//		{
//			availableTime = earlyTime;
//		}
//		if (availableTime > lasteTime)
//		{
//			return false;
//		}
//		availableTime += Li;
//	}
//	return true;
//}
//
//int main()
//{
//	int n;
//	int arr[MAX_N][3];
//	//閺夊牊鎸搁崣?
//	scanf("%d", &n);//濞戞挶鍊楃划宥夊极閻楀牆绁
//	while (n--)
//	{
//		int m;
//		scanf("%d", &m);//閻炴稏鍔庨妵姘掕箛鏇犵煁闁轰胶澧楀畵渚鎯冮崟顐㈡闁哄鐖奸ˉ锝夊嫉?
//		for (int i = 0; i < m; i++)
//		{
//			scanf("%d %d %d", &arr[i][0], &arr[i][1], &arr[i][2]);
//		}
//		//闁告帇鍊栭弻鍥槹閻愬瓨绨氶柡鍕靛灠閹線宕ｉ娆庣鞍閻庣懓顦崣蹇涙⒔瀹ュ牊鍎
//		if (Check_Plane(arr, m))
//		{
//			printf("YES\n");
//		}
//		else {
//			printf("NO\n");
//		}
//	}
//	
//	return 0;
//}

//#include <stdio.h>
//#include <stdlib.h>
//#include <stdbool.h>
//
//#define MAX_N 1000000
//
//// 婵絾妫佺欢婵嬪礄閼恒儲娈堕柨娑樼灱閺併倖绂嶆惔銏犵瑩閹?
//int compare(const void* a, const void* b) {
//    int* planeA = (int*)a;
//    int* planeB = (int*)b;
//    int lasteTimeA = planeA[0] + planeA[1];
//    int lasteTimeB = planeB[0] + planeB[1];
//    return lasteTimeA - lasteTimeB;
//}
//
//// 闁告帇鍊栭弻鍥及椤栨碍鍎婇柛娆樺灟娴滄帞鐟邦槸閸欏繘姊藉鍫熷劙
//bool Check_Plane(int arr[][3], int m) {
//    // 闁圭ǹ顦崺灞炬綇閻愵剚顦ч梻鍌涙綑閹蜂即鎯勫Ο缁橆棆闁哄啫鐖煎Λ鍧楀箳閹烘垹纰
//    qsort(arr, m, sizeof(arr[0]), compare);
//
//    int availableTime = 0; // 閻犵儤鍨挎禍楣冩儍閸曨偄璁查柣鈧妽濡炲倿姊?
//
//    for (int i = 0; i < m; i++) {
//        int Ti = arr[i][0]; // 闁告帗濯介幓顏堝籍閸洘锛
//        int Di = arr[i][1]; // 闁烩晜蓱濡棝寮崼鏇燂紵
//        int Li = arr[i][2]; // 闂傚嫬绉烽幆銈夊籍閸洘锛
//
//        int earlyTime = Ti; // 闁哄牓寮埡鍛栭柦閼恒儲顦ч梻?
//        int lasteTime = Ti + Di; // 闁哄牓寮插鑸殿栭柦閼恒儲顦ч梻?
//
//        // 濠碘冲归悘澶屾崉閹达缚澹曢柣銊ュ瑜版煡鎮介妸锔筋槯闂傚倸鐡ㄥΛ顓熺鎼淬垺浠橀柡鍐ｆ櫊濡剧兘鎷冮懞銉︻槯闂傚倽鎻槐婵嬪礆濞嗘劖绾柡鍌涙緲瑜版煡鎮介妸锔筋槯闂?
//        if (availableTime < earlyTime) {
//            availableTime = earlyTime;
//        }
//
//        // 婵☆偊寮婚妷锔叫﹂柛姘剧畱瑜板弶绂掗妷銉﹁含闁哄牓寮插鑸殿栭柦閼恒儲顦ч梻鍌涙綑婢х姷鐟版湰閸ㄦ岸姊藉鍫熷劙
//        if (availableTime > lasteTime) {
//            return false; // 闁哄啰濮电涵鍓佺懓顦崣蹇涙⒔瀹ュ牊鍎
//        }
//
//        // 闁哄洤鐡ㄩ弻濠勬崉閹达缚澹曢柣銊ュ瑜版煡鎮介妸锔筋槯闂?
//        availableTime += Li;
//    }
//
//    return true; // 闁圭敻寮垫径鎰垫＇闁哄牊妞介崗姗宕ｉ娆庣鞍閻庣懓顦崣蹇涙⒔瀹ュ牊鍎
//}
//
//int main() {
//    int n; // 婵炴潙顑堥惁顖炲极閻楀牆绁﹂柣銊ュ缁秹寮?
//    scanf("%d", &n);
//
//    while (n--) {
//        int m; // 婵絽绻掔划宥夊极閻楀牆绁﹂柣銊ュ椤ワ綁寮甸悜妯绘闂?
//        scanf("%d", &m);
//
//        int arr[MAX_N][3]; // 閻庢稒锚閸嬪秴袙韫囨梻浠稿瀣仦濠ч柣?T_i, D_i, L_i
//
//        // 閺夊牊鎸搁崣鍡椥掕箛鏃備桓濡炲鍋炲┃闁汇劌瀚弳鐔煎箲?
//        for (int i = 0; i < m; i++) {
//            scanf("%d %d %d", &arr[i][0], &arr[i][1], &arr[i][2]);
//        }
//
//
//        // 闁告帇鍊栭弻鍥及椤栨碍鍎婇柛娆樺灟娴滄帞鐟邦槸閸欏繘姊藉鍫熷劙
//        if (Check_Plane(arr, m)) {
//            printf("YES\n");
//        }
//        else {
//            printf("NO\n");
//        }
//    }
//
//    return 0;
//}

//#include<stdio.h>
//#include<stdlib.h>
//
//int T[15], D[15], L[15];
//int n;
//int vis[15], ans;
//
//
//void dfs(int plane, int time)
//{
//	if (plane == n)
//	{
//		ans = 1;
//		return;
//	}
//	for (int i = 0; i < n; i++)
//	{
//		if (!vis[i] && time <= T[i] + D[i])
//		{
//			int t = time;
//			if (t < T[i])
//				t = T[i];
//			vis[i] = 1;
//			dfs(plane + 1, t + L[i]);
//			vis[i] = 0;
//		}
//	}
//}
//int main()
//{
//	int m;
//	scanf("%d", &m);
//	while (m--)
//	{
//		scanf("%d", &n);
//		for (int i = 0; i < n; i++)
//		{
//			scanf("%d %d %d", &T[i], &D[i], &L[i]);
//		}
//		ans = 0;
//		dfs(0, 0);
//		if (ans)
//			printf("YES\n");
//		else
//			printf("NO\n");
//	}
//	return 0;
//}
//#include <stdio.h>
//#include <stdlib.h>
//
//#define N 100
//
//char t[N]; // 鐎规矮绠熸稉娑擃亜鐡х粭锔芥殶缂佸嫸绱濋悽銊ょ艾鐎涙ê鍋嶆禍灞藉级閺嶆垹娈戦懞鍌滃仯
//
//// 閼惧嘲褰囧锕鐡欓懞鍌滃仯閻ㄥ嫮鍌ㄥ?
//int ls(int p) {
//    return p << 1; // 瀹革箑鐡欓懞鍌滃仯閻ㄥ嫮鍌ㄥ鏇熸Ц閻栨儼濡悙鍦偍瀵洜娈崐?
//}
//
//// 閼惧嘲褰囬崣鍐茬摍閼哄倻鍋ｉ惃鍕偍瀵?
//int rs(int p) {
//    return p << 1 | 1; // 閸欏啿鐡欓懞鍌滃仯閻ㄥ嫮鍌ㄥ鏇熸Ц閻栨儼濡悙鍦偍瀵洜娈崐宥呭1
//}
//
//// 楠炲灝瀹虫导妯哄帥閹兼粎鍌ㄩ敍鍦擣S閿涘鍤遍弫?
//void bfs(int root) {
//    int queue[N]; // 鐎规矮绠熸稉娑擃亪妲﹂崚妤嬬礉閻€劋绨涙ê鍋嶅鍛邦問闂傤喚娈戦懞鍌滃仯
//    int front = 0, rear = 0; // 闂冪喎鍨惃鍕仈閸滃苯鐔幐鍥嫛
//
//    queue[rear++] = root; // 鐏忓棙鐗撮懞鍌滃仯閸旂姴鍙嗛梼鐔峰灙
//
//    while (front < rear) { // 瑜版捇妲﹂崚妞剧瑝娑撹櫣鈹栭弮?
//        int u = queue[front++]; // 閸欐牕鍤梼鐔峰灙婢舵挳鍎撮惃鍕Ν閻?
//        printf("%c", t[u]); // 鏉堟挸鍤ぐ鎾冲閼哄倻鍋ｉ惃鍕?
//
//        // 婵″倹鐏夊锕鐡欓懞鍌滃仯鐎涙ê婀敍灞界殺閸忚泛濮為崗銉╂Е閸?
//        if (t[ls(u)]) {
//            queue[rear++] = ls(u);//閸忋儵妲
//        }
//
//        // 婵″倹鐏夐崣鍐茬摍閼哄倻鍋ｇ涙ê婀敍灞界殺閸忚泛濮為崗銉╂Е閸?
//        if (t[rs(u)]) {
//            queue[rear++] = rs(u);
//        }
//    }
//}
//<<<<<<< HEAD
//
//int main() {
//    // 閸掓繂顫愰崠鏍︾癌閸欏鐖查惃鍕Ν閻?
//    t[1] = 'A';
//    t[2] = 'B'; t[3] = 'C';
//    t[4] = 'D'; t[5] = 'E'; t[6] = 'F'; t[7] = 'G';
//    t[9] = 'H'; t[11] = 'I';
//
//    bfs(1); // 娴犲孩鐗撮懞鍌滃仯1瀵慨瀣箻鐞涘瓓FS闁秴宸
//    printf("\n");
//
//    bfs(3); // 娴犲骸鐡欓懞鍌滃仯3瀵慨瀣箻鐞涘瓓FS闁秴宸
//    return 0;
//}
//=======
//int main()
//{
//	int m;
//	scanf("%d", &m);
//	while (m--)
//	{
//		scanf("%d", &n);
//		for (int i = 0; i < n; i++)
//		{
//			scanf("%d %d %d", &T[i], &D[i], &L[i]);
//		}
//		ans = 0;
//		dfs(0, 0);
//		if (ans)
//			printf("YES\n");
//		else
//			printf("NO\n");
//	}
//	return 0;
//}
//P
//>>>>>>> 3e8bb2bf53abc2bc3e28325b5179703f945c24b6
//#include <stdio.h>
//#include <stdlib.h>
//
//// 鐎规矮绠熷Λ瀣磸閻ㄥ嫭娓舵径褍銇囩亸?
//#define MAX_N 400
//#define MAX_M 400
//
//// 鐎规矮绠熸す顒傂╅崝銊ф畱閸忣偂閲滈弬鐟版倻
//const int dx[8] = { 2, 2, -2, -2, 1, 1, -1, -1 };
//const int dy[8] = { 1, -1, 1, -1, 2, -2, 2, -2 };
//
//// 鐎规矮绠熼梼鐔峰灙缂佹挻鐎
//typedef struct {
//    int x, y;
//} Point;
//
//Point queue[MAX_N * MAX_M]; // 闂冪喎鍨
//int front = 0, rear = 0;    // 闂冪喎鍨惃鍕仈閸滃苯鐔
//
//// BFS 閸戣姤鏆
//void bfs(int n, int m, int startX, int startY, int dist[MAX_N + 1][MAX_M + 1]) {
//    // 閸掓繂顫愰崠鏍Е閸?
//    front = rear = 0;
//    queue[rear++] = (Point){ startX, startY }; // 鐏忓棜鎹ｉ悙鐟板閸忋儵妲﹂崚?
//    dist[startX][startY] = 0;               // 鐠ч鍋ｉ惃鍕劄閺侀璐 0
//
//    // BFS 闁秴宸
//    while (front < rear) {
//        Point current = queue[front++]; // 閸欐牕鍤梼鐔碱浕閸忓啰绀
//        int cx = current.x, cy = current.y;
//
//        // 闁秴宸婚崗顐￠嚋閺傜懓鎮
//        for (int i = 0; i < 8; i++) {
//            int nx = cx + dx[i], ny = cy + dy[i];
//
//            // 濡弻銉︽煀娴ｅ秶鐤嗛弰顖氭儊閸︺劍顥愰惄妯垮瘱閸ユ潙鍞存稉鏃婀悮顐ヮ問闂傤喛绻
//            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && dist[nx][ny] == -1) {
//                dist[nx][ny] = dist[cx][cy] + 1; // 閺囧瓨鏌婂銉︽殶
//                queue[rear++] = (Point){ nx, ny }; // 鐏忓棙鏌婃担宥囩枂閸旂姴鍙嗛梼鐔峰灙
//            }
//        }
//    }
//}
//
//int main() {
//    int n, m, x, y;
//    scanf("%d %d %d %d", &n, &m, &x, &y);
//
//    // 閸掓繂顫愰崠鏍獩缁傝崵鐓╅梼纰夌礉閹甸張澶婅壈顔曟稉?-1
//    int dist[MAX_N + 1][MAX_M + 1];
//    for (int i = 1; i <= n; i++) {
//        for (int j = 1; j <= m; j++) {
//            dist[i][j] = -1;
//        }
//    }
//
//    // 鐠嬪啰鏁 BFS 閸戣姤鏆
//    bfs(n, m, x, y, dist);
//
//    // 鏉堟挸鍤紒鎾寸亯
//    for (int i = 1; i <= n; i++) {
//        for (int j = 1; j <= m; j++) {
//            printf("%d ", dist[i][j]);
//        }
//        printf("\n");
//    }
//
//    return 0;
//}
//#include<stdio.h>
//#include<stdlib.h>
//#include<stdbool.h>
//int N;
//#define MAX_N 210
//int vis[MAX_N][MAX_N];
//int xx[100];
//int yy[100];
//int front, rear;
//typedef struct
//{
//	int x;
//	int y;
//}point;
//
//point queue[MAX_N * MAX_N];
//point dequeue()
//{
//	return queue[front++];
//}
//
//
//void enqueue(int x, int y)
//{
//	queue[rear].x = x;
//	queue[rear].y = y;
//	rear++;
//}
//bool empty() {
//	return front == rear;//澶村拰灏剧浉绛夊氨鏄┖
//}
//
//bool bfs(int x, int y)
//{
//	front = rear = 0;
//	enqueue(x, y);
//	vis[x][y] = 1;
//	while (!empty())
//	{
//		point p = dequeue();//鍙栧ご缁撶偣
//		for (int i = 0; i < N; i++)
//		{
//			int nx = p.x + xx[i];
//			int ny = p.y + yy[i];
//			if (nx >= 0 && nx < MAX_N && ny >= 0 && ny < MAX_N && !vis[nx][ny])
//			{
//				vis[nx][ny] = 1;//宸茬粡璧拌繃浜
//				enqueue(nx, ny);//鍏ラ槦鍒
//
//			}
//		}
//	}
//	//妫鏌ユ墍鏈夌殑鐐规槸鍚﹁璁块棶
//	for (int i = 0; i < MAX_N; i++)
//	{
//		for (int j = 0; j < MAX_N; j++)
//		{
//			if (!vis[i][j])
//			{
//				return false;
//			}
//		}
//	}
//	return true;
//}
//
//
//int main()
//{
//	//杈撳叆
//	int T;
//	scanf("%d", &T);
//	while (T--)
//	{
//		scanf("%d", &N);
//		memset(vis, 0, sizeof(vis));
//		for (int i = 0; i < N; i++)
//		{
//			scanf("%d %d", &xx[i], &yy[i]);
//		}
//		if (bfs(MAX_N/2, MAX_N/2))
//			printf("YES\n");
//		else
//			printf("NO\n");
//	}
//	return 0;
//}

//鑷繁鐨勫啓鐨
//#include<stdio.h>
//#include<stdlib.h>
//#define MAX_N 1000000
//int arr[MAX_N];
//
//
//void Swap(int* x, int* y)
//{
//	int tmp = 0;
//	tmp = *x;
//	*x = *y;
//	*y = tmp;
//}
//int main()
//{
//	int x,n,y=0;
//	//杈撳叆
//	scanf("%d", &n);
//	for (int i = 0; i < n; i++)
//	{
//		scanf("%d", &arr[i]);
//	}
//	//鍒ゆ柇鏄笉鏄渶灏
//	for (int x = 0; x < n; x++)//澶栧洿涓嬫爣
//	{
//		for (int y = x + 1; y < n; y++)
//		{
//			if (arr[y] < arr[x])
//			{
//				Swap(&arr[x], &arr[y]);
//			}
//		}
//	}
//	for (int i = 0; i <n; i++)
//	{
//		printf("%d ", arr[i]);
//	}
//}

//涔︿笂鐨
//#include<stdio.h>
//#include<stdlib.h>
//int a[1000005], n;
//
//void Swap(int* x,int* y)
//{
//<<<<<<< HEAD
//	int tmp;
//	tmp = *y;
//	*y = *x;
//	*x = tmp;
//=======
//	queue[rear].x = x;
//	queue[rear].y = y;
//	rear++;
//}
//bool empty() {
//	return front == rear;//婢舵潙鎷扮亸鍓ф祲缁涘姘ㄩ弰顖溾敄
//>>>>>>> 88ae4462aa1f8a5c546bcaf10a2d7f6b8f3d3e6e
//}
//void selection_sort()
//{
//	for (int i = 0; i < n-1; i++)
//	{
//<<<<<<< HEAD
//		int m = i;//m璁板綍鏈灏忕殑鏁颁綅缃
//		for (int j = i + 1; j < n; j++)
//		{
//			if (a[j] < a[i])
//				m = j;
//=======
//		point p = dequeue();//閸欐牕銇旂紒鎾跺仯
//		for (int i = 0; i < N; i++)
//		{
//			int nx = p.x + xx[i];
//			int ny = p.y + yy[i];
//			if (nx >= 0 && nx < MAX_N && ny >= 0 && ny < MAX_N && !vis[nx][ny])
//			{
//				vis[nx][ny] = 1;//瀹歌尙绮＄挧鎷岀箖娴?
//				enqueue(nx, ny);//閸忋儵妲﹂崚?
//
//			}
//>>>>>>> 88ae4462aa1f8a5c546bcaf10a2d7f6b8f3d3e6e
//		}
//		Swap(&a[i], &a[m]);
//	}
//<<<<<<< HEAD
//=======
//	//濡弻銉﹀閺堝娈戦悙瑙勬Ц閸氾箒顫︾拋鍧楁６
//	for (int i = 0; i < MAX_N; i++)
//	{
//		for (int j = 0; j < MAX_N; j++)
//		{
//			if (!vis[i][j])
//			{
//				return false;
//			}
//		}
//	}
//	return true;
//>>>>>>> 88ae4462aa1f8a5c546bcaf10a2d7f6b8f3d3e6e
//}
//int main()
//{
//<<<<<<< HEAD
//	scanf("%d", &n);
//	for (int i = 0; i < 5; i++)
//=======
//	//鏉堟挸鍙
//	int T;
//	scanf("%d", &T);
//	while (T--)
//>>>>>>> 88ae4462aa1f8a5c546bcaf10a2d7f6b8f3d3e6e
//	{
//		scanf("%d", &a[i]);
//	}
//	selection_sort();
//	for (int i = 0; i < n; i++)
//	{
//		printf("%d ", a[i]);
//	}
//}

//鍐掓场鎺掑簭
//#include<stdio.h>
//#include<stdlib.h>
//#include<stdbool.h>
//#define MAX_N 20000
//int arr[MAX_N];
//void Swap(int* x, int* y)
//{
//	int tmp;
//	tmp = *x;
//	*x = *y;
//	*y = tmp;
//}
//int main()
//{
//	int n;
//	scanf("%d", &n);
//	for (int i = 0; i < n; i++)
//	{
//		scanf("%d", &arr[i]);
//	}
//	for (int i = 0; i < n-1; i++)
//	{
//		bool t = false;//杩樻病鏈変氦鎹
//		for (int j = 0; j < n - i - 1; j++)
//		{
//			if (arr[j] > arr[j + 1])
//			{
//				Swap(&arr[j], &arr[j + 1]);
//				t = true;
//				if (!t)
//				{
//					break;
//				}
//			}
//		}
//	}
//	for (int i = 0; i < n; i++)
//	{
//		printf("%d ", arr[i]);
//	}
//}
//1`  


//鎻掑叆鎺掑簭a
//#include<stdio.h>
//#include<stdlib.h>
//#include<stdbool.h>
//#define MAX_N 100000
//int arr[MAX_N];
//int n;
//
//void insert_sort()
//{
//	for (int i = 1; i < n; i++)//i缁欑殑绗簩涓暟瀛楋紝璁﹋鎸囧悜鍓嶄竴涓暟瀛楋紝濂芥瘮杈冦
//	{
//		int key;
//		key = arr[i];
//		int j = i - 1;
//		while (j >= 0 && arr[j] > key)
//		{
//			arr[j + 1] = arr[j];
//			j--;
//		}
//		arr[j+1] = key;//鎻掑叆
//	}
//}
//int main()
//{
//	scanf("%d", &n);
//	for (int i = 0; i < n; i++)
//	{
//		scanf("%d", &arr[i]);//杩欓噷涓嶈鍐欑┖鏍间簡锛燂紵锛燂紵锛燂紵锛燂紵
//	}
//	insert_sort();
//	for (int i = 0; i < n; i++)
//	{
//		printf("%d ", arr[i]);
//	}
//	return 0;
//}


//qsort
//



//#include <stdio.h>
//#include <stdlib.h>
//
//int main(int argc, char* argv[])
//{
//	//鍋囧姣忎釜浜洪兘鎻℃墜浜嗭紝閭ｅ氨鏄0*49锛0涓汉姣忎釜閮芥彙49娆★級
//	//鍘绘帀閲嶅鐨勬墍浠0*49/2
//	//鐒跺悗鍚岀悊姹傚嚭涓冧釜浜虹浉浜掓彙鎵嬫鏁板垹鎺
//	int a = 50 * 49 / 2 - 7 * 6 / 2;
//	printf("%d", a);
//	return 0;
//}
//#include<stdio.h>
//#include<stdlib.h>
//int main()
//{
//	int sum = 0;
//	sum = 50 * 49;
//	sum /= 2;
//	int sum2 = 0;
//	sum2 = 7 * 6 / 2;
//	int time = 0;
//	time = sum - sum2;
//	printf("%d", time);
//}
//#include <stdio.h>
//#include <stdlib.h>
//#include <math.h> 
//
//#define length 343720
//#define height 233333
//typedef long long Long;
//
//int main(int argc, char* argv[])
//{
//    for (Long i = 1;; i++)
//        if ((Long)(17 * i) % height == 0 && (Long)(15 * i) % length == 0) {
//            printf("%0.2lf", 2 * sqrt(15 * 15 * i * i + 17 * 17 * i * i));
//            break;
//        }
//    return 0;
//}

//#include<stdio.h>
//#include<stdlib.h>
//#include<stdbool.h>
//
//bool check_good(int num)
//{//褰撳墠浣嶆暟
//	int pos = 1;
//	while (num>0)
//	{
//		int dig=num % 10;
//		if (pos % 2 == 1)
//		{
//			if (dig % 2 == 0)
//				return false;
//		}
//		else {
//			if (dig % 2 == 1)
//				return false;
//		}
//		num /= 10;//鍙栨帀鏈鍚庝竴浣
//		pos++;
//	}
//	return true;
//}
//
//int main()
//{
//	int N;
//	int data=0;
//	scanf("%d", &N);
//	//涓綅銆佺櫨浣嶃佷竾浣嶆槸濂囨暟
//	//鍗佷綅銆佸崈浣嶃佸崄涓囦綅鏄伓鏁
//	for (int i = 1; i <= N; i++)//閬嶅巻姣忎釜鏁板瓧
//	{
//		//鎵句釜浣嶃佸崄浣嶃佺櫨浣
//		//闄ゆ硶鍜屽彇浣欐眰姣忎竴浣嶆暟瀛
//		if (check_good(i))
//		{//i鏄綋鍓嶆暟瀛
//			data++;
//		}
//	}
//	printf("%d", data);
//	return 0;
//}

//#include <stdio.h>
//#include <stdbool.h>
//
//// 鍒ゆ柇涓涓暟鏄惁鏄滃ソ鏁扳
//bool isGoodNumber(int num) {
//    int position = 1; // 浣嶆暟锛屼粠涓綅寮濮
//    while (num > 0) {
//        int digit = num % 10; // 鍙栧嚭褰撳墠浣嶇殑鏁板瓧
//        if (position % 2 == 1) {
//            // 濂囨暟浣嶏紙涓綅銆佺櫨浣嶃佷竾浣嶇瓑锛夊繀椤绘槸濂囨暟
//            if (digit % 2 == 0) {
//                return false;
//            }
//        }
//        else {
//            // 鍋舵暟浣嶏紙鍗佷綅銆佸崈浣嶃佸崄涓囦綅绛夛級蹇呴』鏄伓鏁
//            if (digit % 2 == 1) {
//                return false;
//            }
//        }
//        num /= 10; // 鍘绘帀鏈鍚庝竴浣
//        position++; // 浣嶆暟澧炲姞
//    }
//    return true;
//}
//
//int main() {
//    int N;
//    int data = 0;
//    scanf("%d", &N);
//
//    // 閬嶅巻姣忎釜鏁板瓧锛屽垽鏂槸鍚︽槸鈥滃ソ鏁扳
//    for (int i = 1; i <= N; i++) {
//        if (isGoodNumber(i)) {
//            data++;
//        }
//    }
//
//    printf("%d\n", data);
//    return 0;
//}
//%50
//#include<stdio.h>
//#include<stdlib.h>
//#include<math.h>
//int main()
//{
//	int n = 0;
//	double d;
//	scanf("%d %f,", &n, &d);
//	double result = d * pow(2, n);//骞虫柟
//	long long rounder = (long long)(result + 0.5);
//	printf("%11d\n", rounder);
//	return 0;
//}
//35
//#include <stdio.h>
//#include <math.h>
//
//int main() {
//    int n;
//    float d;
//    scanf("%d %f", &n, &d);
//
//    // 灏嗘诞鐐规暟涔樹互 2^n
//    float result = d * pow(2, n);
//
//    // 鍥涜垗浜斿叆鍒版渶鎺ヨ繎鐨勬暣鏁
//    result = round(result);
//
//    // 杈撳嚭缁撴灉
//    printf("%.0f\n", result);
//
//    return 0;
//}

//#include <stdio.h>
//#include <string.h>
//
//#define N 2000
//
//int mul(int a[], int lenA, int b, int c[]) {
//    int lenC = 0;
//
//    for (int i = 0, t = 0; i < lenA || t; i++) {
//        if (i < lenA) t += a[i] * b;
//        c[lenC++] = t % 10;
//        t /= 10;
//    }
//
//    return lenC;
//}
//
//int add(int a[], int lenA, int b[], int lenB, int c[]) {
//    int lenC = lenA > lenB ? lenA : lenB;
//
//    int t = 0;
//    for (int i = 0; i < lenC; i++) {
//        if (i < lenA) t += a[i];
//        if (i < lenB) t += b[i];
//        c[i] = t % 10;
//        t /= 10;
//    }
//
//    if (t) {
//        c[lenC] = 1;
//        return lenC + 1;
//    }
//
//    return lenC;
//}
//
//int main() {
//    int n;
//    char str[1050];
//    scanf("%d %s", &n, str);
//
//    char* dot = strchr(str, '.');
//    int lenF = strlen(dot + 1);
//    char fraction_part[lenF + 1];
//    strcpy(fraction_part, dot + 1);
//
//    *dot = '\0';
//    strcat(str, fraction_part);
//    int len = strlen(str);
//
//    int Num[N];
//    for (int i = 0; i < len; i++) Num[i] = str[len - 1 - i] - '0';
//
//    int lenNum = len;
//    for (int i = 0; i < n; i++) {
//        int ans[N] = { 0 };
//        lenNum = mul(Num, lenNum, 2, ans);
//        for (int i = 0; i < lenNum; i++) Num[i] = ans[i];
//    }
//
//    int integer[N] = { 0 };
//    int pos = 0;
//    for (int i = lenF; i <= lenNum - 1; i++) {
//        integer[pos++] = Num[i];
//    }
//
//    int lenInteger = pos;
//    if (Num[lenF - 1] >= 5) {
//        int ans2[N] = { 0 };
//        int one[1] = { 1 };
//        lenInteger = add(integer, lenInteger, one, 1, ans2);
//        for (int i = 0; i < lenInteger; i++) integer[i] = ans2[i];
//    }
//    for (int i = lenInteger - 1; i >= 0; i--) printf("%d", integer[i]);
//    return 0;
//}

//#include<stdio.h>
//#include<string.h>
//
//int main()
//{
//	char str[] = "hello, world!";
//	char* result = strchr(str, 'w');
//	printf("Found 'W' at position: %ld\n", result-str);//璁＄畻鎸囬拡鐨勫亸绉婚噺
//}
////result鏄竴涓寚閽堬紝鑰屾寚閽堟槸涓涓唴瀛樻寚閽堬紝鍦–璇█涓紝鎸囬拡鐨勫奸氬父鏄竴涓棤绗﹀彿鏁存暟锛岃〃绀哄唴瀛樹腑鐨勬煇涓湴鍧


//#include<stdio.h>
//#include<string.h>
//int  main()
//{
//	char str[] = "hello,world";
//	size_t length = strlen(str);
//	printf("%zu\n", length);//zu%鎵撳嵃鏃犵鍙锋暟銆
//	return 0;
//}

//#include<stdio.h>
//#include<string.h>
//
//int main()
//{
//	char src[] = "hello, world!";
//	char dest[50];
//	strcpy(dest, src);
//	printf("%s\n", src);
//	printf("%s\n", dest);
//}

//杩藉姞瀛楃涓
//#include<stdio.h>
//#include<string.h>
//int main()
//{
//	char dest[50] = "hello";
//	char src[] = "world!";
//	strcat(dest, src);
//	printf("%s\n", dest);
//	return 0;
//}

//#include<stdio.h>
//#include<stdlib.h>
//
//int main()
//{
//	int arr[100] = {5, 6, 8, 6, 9, 1, 6, 1, 2, 4, 9, 1, 9, 8, 2, 3, 6, 4, 7, 7,
//                    5, 9, 5, 0, 3, 8, 7, 5, 8, 1, 5, 8, 6, 1, 8, 3, 0, 3, 7, 9,
//                    2, 7, 0, 5, 8, 8, 5, 7, 0, 9, 9, 1, 9, 4, 4, 6, 8, 6, 3, 3,
//                    8, 5, 1, 6, 3, 4, 6, 7, 0, 7, 8, 2, 7, 6, 8, 9, 5, 6, 5, 6,
//                    1, 4, 0, 1, 0, 0, 9, 4, 8, 0, 9, 1, 2, 8, 5, 0, 2, 5, 3, 3 };
//    int R[13] = { 0,31,28,31,30,31,31,30,31,30,30,31,31 };
//    int year = 0;
//    int month = 1;
//    int day = 1;
//    int sum = 0;
//    for ( month = 1; month <= 13; month++)
//    {
//        for (day = 1; day <= R[month]; day++)
//        {
//            int R[8] = { 2,0,2,3,month / 10,month % 10,day / 10,day % 10 };
//            int i, k=0;
//            for (i = 0; i < 100; i++)
//            {
//                if (arr[i] == R[k])
//                {
//                    k++;
//                    if (k == 8)
//                    {
//                        sum++;
//                        break;
//                    }
//                }
//            }
//        }
//    }
//    printf("%d", sum);
//    return 0;
//}

//#include<stdio.h>
//#include<stdlib.h>
//
//int main()
//{
//    int arr[100] = { 5, 6, 8, 6, 9, 1, 6, 1, 2, 4, 9, 1, 9, 8, 2, 3, 6, 4, 7, 7,
//                     5, 9, 5, 0, 3, 8, 7, 5, 8, 1, 5, 8, 6, 1, 8, 3, 0, 3, 7, 9,
//                     2, 7, 0, 5, 8, 8, 5, 7, 0, 9, 9, 1, 9, 4, 4, 6, 8, 6, 3, 3,
//                     8, 5, 1, 6, 3, 4, 6, 7, 0, 7, 8, 2, 7, 6, 8, 9, 5, 6, 5, 6,
//                     1, 4, 0, 1, 0, 0, 9, 4, 8, 0, 9, 1, 2, 8, 5, 0, 2, 5, 3, 3 };
//    int R[13] = { 0,31,28,31,30,31,31,30,31,30,30,31,31 };
//    int month=1;
//    int day = 1;
//    int sum = 0;
//    for (month = 1; month <= 12; month++)
//    {
//        for (day = 1; day <= R[month]; day++)
//        {
//            int R[8] = { 2,0,2,3,month / 10,month % 10,day / 10,day % 10 };
//            int i, k=0;
//            for (i = 0; i < 100; i++)
//            {
//                if (arr[i] == R[k])
//                {
//                    k++;
//                    if (k == 8)
//                    {
//                        sum++;
//                        break;
//                    }
//                }
//            }
//        }
//    }
//    printf("%d", sum);
//    return 0;
//}

//01涓茬殑鐔
//#include<stdio.h>
//#include<stdlib.h>
//
//int main()
//{
//	double n = 23333333;
//	double sum;
//	int j;
//	for (j=n/2;j>=0;j--)
//	{
//		sum = 0;
//		sum = sum - j * (j / n) * log2(j / n);
//		sum = sum - (n - j) * ((n - j) / n) * log2((n - j) / n);
//		//鍒ゆ柇鏄惁鍦ㄨ寖鍥翠箣鍐
//		if (sum > 11625907.5 && sum < 11625907.6)
//		{
//			break;
//		}
//	}
//	printf("%d", j);
//	return 0;
//}

//閲戝睘
//#include<math.h>
//#include<stdio.h>
//#include<stdlib.h>
//#define MAX_N 100000
//long N;
//long long A;
//long long B;
//long long V=0;
//
//int compare(const void* a, const void* b)
//{
//	return (*(int*)a - *(int*)b);
//}
//int main()
//{
//	int min;
//	int max;
//	int arr[MAX_N];
//	//杈撳叆
//	scanf("%d", &N);
//	for (int i = 0; i < N; i++)
//	{
//		scanf("%d %d", &A, &B);
//	}
//	while (N > 0)
//	{
//		for (int i = 0; i < N; i++)
//		{
//			if ((A / V) == B)
//			{
//				arr[i] = V;
//				N--;
//			}
//		}
//		int n = sizeof(arr) / sizeof(arr[0]);
//		//鎶奦鏀捐繘鍘诲悗锛屽啀鎵炬渶澶у拰鏈灏
//		qsort(arr, n, sizeof(int), compare);
//		for (int i = 0; i < N; i++)
//		{
//			if (arr[i] != 0)
//			{
//				min = arr[i];
//				break;
//			}
//		}
//	}
//	printf("%d", min);
//}
//#include <stdio.h>
//#include <stdlib.h>
//
//#define MAX_N 100000
//int A, B;
//int compare(const void* a, const void* b) {
//    return (*(int*)a - *(int*)b);
//}
//
//int main() {
//    int N;
//    int arr[MAX_N];
//    int count = 0;
//
//    // 杈撳叆 N
//    scanf("%d", &N);
//    for (int i = 0; i < N; i++)
//    {
//        scanf("%d %d", &A, &B); 
//        for (int V = 1; V < MAX_N; V++)
//        {
//            if ((A / V) == B)//???鍙绛変簬B灏辫緭鍏
//            {
//                arr[count++] = V;
//            }
//        }
//    }
//    
//
//    // 瀵规暟缁勮繘琛屾帓搴
//    qsort(arr, count, sizeof(int), compare);
//
//    // 鎵惧埌鏈灏忓
//    int min = arr[0];
//    int max = arr[N-1];
//    // 杈撳嚭鏈灏忓
//    printf("%d %d\n", min,max);
//    
//    return 0;
//}
//#include<stdio.h>
//int main() {
//    int n, a, b, d, i, c, e = 0, t = 1000000000;
//    scanf("%d", &n);
//    for (i = 1; i <= n; i++) {
//        scanf("%d %d", &a, &b);
//        d = a / b;
//        c = a / (b + 1) + 1;
//        //涓夌粍鏁版嵁锛宒鍜宑宸茬粡绠楃殑鏄渶澶у拰鏈灏忓硷紝姣旇緝涓夌粍鏁版嵁涓渶澶у拰鏈灏忓肩殑澶у皬锛屽彇鏈澶х殑銆
//        if (c > e)
//            e = c;
//        if (t > d)
//            t = d;
//    }
//    printf("%d %d", e, t);
//
//    return 0;
//}

<<<<<<< HEAD
//#include<stdio.h>
//#include<stdlib.h>
//int n;
//int Ti[15], Di[15], Li[15];
//int vis[15], ans;
//void dfs(int step, int end)
//{
//	if (step == n)
//	{
//		ans = 1;
//		return;
//	}
//	for (int i = 0; i < end; i++)
//	{
//		if (!vis[i] && end < Ti[i] + Di[i])
//		{
//			int t = end;
//			if (t < Ti[i])
//			{
//				t = Ti[i];
//			}
//			vis[i] = 1;//已经用过
//			dfs(step + 1, t + Li[i]);
//			vis[i] = 0;
//		}
//	}
//}
//int main()
//{
//	scanf("%d", &n);
//	int m;
//	while (m--)
//	{
//		scanf("%d", &m);
//		for (int i = 0; i < m; i++)
//		{
//			scanf("%d %d %d", &Ti[i], &Di[i], &Li[i]);
//		}
//		ans = 0;
//		dfs(0, 0);
//		if (ans)
//			printf("YES\n");
//		else
//			printf("NO\n");
//	}
//	return 0;
//}

//#include<stdio.h>
//#include<stdlib.h>
//
//int main()
//{
//	int month=1, day = 1;
//	int year = 2022;
//	int sum = 0;
//	int R[13] = { -1,31,28,31,30,31,30,31,31,30,31,30,31 };
//	if ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0))
//	{
//		//闰年29天
//		R[2] = 29;
//	}
//	int arr[10] = { 0,1,2,3,4,5,6,7,8,9 };
//	
//	for (month = 1; month <= 12; month++)
//	{
//		for (day = 1; day <= R[month]; day++)
//		{
//			int D[8] = { 2,0,2,2,month/10,month%10,day/10,day%10 };
//			for (int i = 0; i < 10; i++)
//			{
//				for (int j = 3; j < 9; j++)
//				{
//					if (D[j+1] == arr[D[j]+1])
//					{
//						int v = 0;
//						v++;
//						if (v == 3)
//						{
//							sum++;
//						}
//					}
//				}
//			}
//		}
//	}
//	printf("%d", sum);
//	return 0;
//}
//#include <stdio.h>
//#include <stdlib.h>
//
//int main() {
//    int month = 1, day = 1;
//    int year = 2022;
//    int sum = 0;
//    int R[13] = { -1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
//
//    // 判断闰年
//    if ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0)) {
//        R[2] = 29; // 闰年2月有29天
//    }
//
//    // 遍历每个月
//    for (month = 1; month <= 12; month++) {
//        // 遍历每一天
//        for (day = 1; day <= R[month]; day++) {
//            // 将日期格式化为数组，例如2022年1月1日 -> {2,0,2,2,0,1,0,1}
//            int D[8] = { 2, 0, 2, 2, month / 10, month % 10, day / 10, day % 10 };
//
//            // 检查是否有连续递增的数字
//            int v = 0; // 记录连续递增的次数
//            for (int j = 0; j < 7; j++) {
//                if (D[j + 1] == D[j] + 1) {
//                    v++;
//                    if (v == 3) { // 如果有3个连续递增的数字
//                        sum++;
//                        break; // 跳出循环，避免重复计数
//                    }
//                }
//                else {
//                    v = 0; // 重置计数器
//                }
//            }
//        }
//    }
//
//    printf("%d\n", sum); // 输出满足条件的日期数量
//    return 0;
//}

#include <stdio.h>
#include <stdlib.h>

int main() {
    int month = 1, day = 1;
    int year = 2022;
    int sum = 0;
    int R[13] = { -1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };

    // 判断闰年
    if ((year % 4 == 0 && year % 100 != 0) || (year % 400 == 0)) {
        R[2] = 29; // 闰年2月有29天
    }

    // 遍历每个月
    for (month = 1; month <= 12; month++) {
        // 遍历每一天
        for (day = 1; day <= R[month]; day++) {
            // 将日期格式化为数组，例如2022年1月1日 -> {2,0,2,2,0,1,0,1}
            int D[8] = { 2, 0, 2, 2, month / 10, month % 10, day / 10, day % 10 };

            // 检查是否有3个连续递增的数字
            for (int j = 0; j < 6; j++) { // 只需要检查前6个元素，因为要比较 D[j], D[j+1], D[j+2]
                if (D[j + 1] == D[j] + 1 && D[j + 2] == D[j + 1] + 1) {
                    sum++; // 满足条件，计数器加1
                    break; // 跳出循环，避免重复计数
                }
            }
        }
    }

    printf("%d\n", sum); // 输出满足条件的日期数量
    return 0;
}
=======
#include<stdio.h>
#include<stdlib.h>
int n;
int Ti[15], Di[15], Li[15];
int vis[15], ans;
void dfs(int step, int end)
{
	if (step == n)
	{
		ans = 1;
		return;
	}
	for (int i = 0; i < end; i++)
	{
		if (!vis[i] && end < Ti[i] + Di[i])
		{
			int t = end;
			if (t < Ti[i])
			{
				t = Ti[i];
			}
			vis[i] = 1;//宸茬粡鐢ㄨ繃
			dfs(step + 1, t + Li[i]);
			vis[i] = 0;
		}
	}
}
int main()
{
	scanf("%d", &n);
	int m;
	while (m--)
	{
		scanf("%d", &m);
		for (int i = 0; i < m; i++)
		{
			scanf("%d %d %d", &Ti[i], &Di[i], &Li[i]);
		}
		ans = 0;
		dfs(0, 0);
		if (ans)
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}
>>>>>>> 9de18d61a96b701f1f31a0e08b845219e0b3a883
